package com.ruoyi.learn.java.algorithm.dp;

/**
 * 2. 完全背包问题（Unbounded Knapsack）
 * 问题特点：每个物品可以选择无限次（可重复放入）。
 * 核心解法：动态规划（与 0-1 背包的区别在于遍历顺序）
 * 定义 dp[j] 同上。
 * 状态转移：对每个物品 i，从小到大遍历容量 j（允许重复选择）：
 * dp[j] = max(dp[j], dp[j - w[i]] + v[i])
 * 时间复杂度：O (nW)。
 */
public class UnboundedKnapsack {
    /**
     * 求解完全背包问题
     * @param weights 物品重量数组
     * @param values 物品价值数组
     * @param capacity 背包容量
     * @return 能获得的最大价值
     */
    public static int maxValue(int[] weights, int[] values, int capacity) {
        // 检查输入合法性
        if (weights == null || values == null || weights.length != values.length || capacity < 0) {
            return 0;
        }

        int n = weights.length;
        // dp[j]表示容量为j的背包能获得的最大价值
        int[] dp = new int[capacity + 1];

        // 遍历每个物品
        for (int i = 0; i < n; i++) {
            // 从小到大遍历容量，允许重复选择当前物品
            for (int j = weights[i]; j <= capacity; j++) {
                // 状态转移方程：取不选当前物品和选当前物品的最大值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        return dp[capacity];
    }

    public static void main(String[] args) {
        // 示例测试
        int[] weights = {2, 3, 4, 5};  // 物品重量
        int[] values = {3, 4, 5, 6};   // 物品价值
        int capacity = 8;              // 背包容量

        System.out.println("最大价值为：" + maxValue(weights, values, capacity));  // 输出：10
        // 解释：选择4次重量为2的物品，总重量8，总价值3×4=12？不，正确解是选择2次重量3和1次重量2：4×2+3=11？
        // 实际正确解：选择2个重量为3的物品(价值4×2=8)和1个重量为2的物品(价值3)，总重量8，总价值11
    }
}
